/*
 * Michigan State University
 * 
 * CSE 410 Summer 2011
 * Computer Project 3
 * 
 * Eric Dostie
 * Jason Harris
 * Grayson Wright
 * 
 */

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <string.h>
#include <stdlib.h>
#include <queue>
using namespace std;

/*
 * A basic class to maintain arrival time / running time parings
 */
class ProcessArrivalEvent {
public:
	int arrivalTime ;
	int runningTime ;
	int processId   ;
	int activeTime	;
	ProcessArrivalEvent();
	int remainingTime();
	bool complete();
	string toString();
};

ProcessArrivalEvent::ProcessArrivalEvent(){
	arrivalTime = -1;
	runningTime = -1;
	processId   = -1;
	activeTime	=  0;
}

string ProcessArrivalEvent::toString(){
	stringstream outString;
	outString <<"id "<< processId<< " arrive " << arrivalTime << "  running " << runningTime;
	return outString.str();
}

int ProcessArrivalEvent::remainingTime(){
	return (runningTime - activeTime);
}

bool ProcessArrivalEvent::complete(){
	return activeTime >= runningTime;
}

/*
 * A basic class to maintain scheduling data
 */
class ProcessSwapEvent {
public:
	int eventTime ;
	int processId   ;
	ProcessSwapEvent();
	string toString();
};


ProcessSwapEvent::ProcessSwapEvent(){
	eventTime = -1;
	processId   = -1;
}

string ProcessSwapEvent::toString(){
	stringstream outString;
	outString << " eventTime " << eventTime<<" id "<< processId ;
	return outString.str();
}


/*
 * Parse the named file into a series of process arrival events.
 * Each will have a process arrival time and projected running time.
 * You can assume the sequence will be in order.  In other words, you
 * shouldn't get arrival time of 5 after arrival time of 20.
 */
vector<ProcessArrivalEvent> getProcessArrivalSequence(char* filename){
	vector<ProcessArrivalEvent> vectorOfArrivalEvents;
	string line;
	int processId = 0;
	// read in the file one line at a time
	ifstream processSourceStream(filename);
	while (processSourceStream.good()){
		getline(processSourceStream, line);
		// if the line is nonempty (it better have 2 tokens, otherwise seqfault
		if (line.size() > 1){
			ProcessArrivalEvent newEvent;
			char charLine[255];
			// tokenize the string into an arrival time and running time
			strcpy(charLine, line.c_str());
			char* firstToken = strtok(charLine, " ");
			newEvent.arrivalTime = atoi(firstToken);
			newEvent.processId = processId;
			processId++ ;

			char*  secondToken = strtok(NULL, " ");
			newEvent.runningTime = atoi(secondToken);
			// add it to the list
			vectorOfArrivalEvents.insert(vectorOfArrivalEvents.end(), 1, newEvent);
		}
	}
	processSourceStream.close();
	return vectorOfArrivalEvents;
}


void writeOutputToFile(vector<ProcessSwapEvent> scheduledList, char* filename){
	ofstream outputFile;
	outputFile.open(filename);
	for (unsigned eventIndex = 0; eventIndex < scheduledList.size(); eventIndex++){
		ProcessSwapEvent nextEvent = scheduledList.at(eventIndex);
		outputFile << nextEvent.toString()<< endl;
	}
	outputFile.close();

}

vector<ProcessSwapEvent>  firstComeFirstServeScheduler(vector <ProcessArrivalEvent> incomingProcessList){
	 vector<ProcessSwapEvent> listOfSchedulingEvents;
	// CSE410DO
	cout << "in first come first served "<< endl;
	int processCount = incomingProcessList.size();
	double cumulativeResponseRatio, responseRatio, cumulativeWait, cumulativeRun;
	// put the real response ratio here
	// CHANGED fixed loop now couts the response ratio per process
	int totalTime = 0;
	bool looping = true;
	unsigned index = 0;
	while( looping && index < incomingProcessList.size() ){
		if( totalTime >= incomingProcessList[index].arrivalTime){
			// fetch waiting time
			float waitingTime = totalTime - incomingProcessList[index].arrivalTime;
			cumulativeWait += waitingTime;
			cumulativeRun += incomingProcessList[index].runningTime;
			// Create a temporary ProcessSwapEvent to store values
			ProcessSwapEvent tempPSE;
			// Set the event ID's
			tempPSE.processId = incomingProcessList[index].processId;
			// Set the start time of the PSE.  Note the first one will start at 0
			// the next one will start at the running time of the previous plus previous time
			tempPSE.eventTime = totalTime;
			// push the temp PSE to our return vector
			listOfSchedulingEvents.push_back(tempPSE);
			// cout the response ratio (w + s) / s.  
			// (waiting time + running time) / running time, where waiting time is the total time
			responseRatio = (totalTime - (double)incomingProcessList[index].arrivalTime)/(double)incomingProcessList[index].runningTime + 1;
			cumulativeResponseRatio += responseRatio;
			cout << "Response ratio: "<< responseRatio << endl;
			// update the total time
			totalTime += incomingProcessList[index].runningTime;
			index++;
		}else{
			totalTime++;
		}
	}
	cout << "Average Response Ratio: " << cumulativeResponseRatio / (double)processCount << endl;
	cout << "Cumulative Response Ratio: " << (cumulativeWait / (double)cumulativeRun) + 1 << endl;
	return listOfSchedulingEvents;
}

vector<ProcessSwapEvent>  shortestProcessNext(vector <ProcessArrivalEvent> incomingProcessList){
	vector<ProcessSwapEvent> listOfSchedulingEvents;
	cout << "in shortest process next "<< endl;
	
	// set up variables for calculations
	float processCount = incomingProcessList.size();
	float cumulativeWait = 0;
	float cumulativeRun = 0;
	float averageResponseRatio = 0;
	
	// loop incrementing time
	// select an arrived process with shortest runtime
	// push back the process to return vector
	// cout response ratio
	// modify time variable to skip over looping while a process is 'executing'
	// cout response ratio (time + runtime of process) / (runtime of process)
	for (int time = 0; true; time++)
	{
		// break when we have no more processes to handle
		if (incomingProcessList.empty()) break;
		
		float runtime = -1;
		int index = -1;
		// since index is set to -1 always, check every time value for a process to run
		// since we update time manually below we aren't wasting time checking while a process is 'executing'
		if (index == -1)
		{
			// nested loop through the vector
			for (int i = 0; i < incomingProcessList.size(); i++)
			{
				// if current time >= to incomplete process arrival time
				// (arrived processes to choose from)
				if (time >= incomingProcessList[i].arrivalTime)
				{
					// if runtime has not yet been set
					if (runtime == -1)
					{
						runtime = incomingProcessList[i].runningTime;
						index = i;
					}
					// else check if this process has a faster runtime than process at pList[index]
					else
					{
						if (incomingProcessList[i].runningTime < runtime)
						{
							runtime = incomingProcessList[i].runningTime;
							index = i;
						}
					}
				}
			}
		}
		
		// found a process to execute if index is legitimate
		if (index >= 0)
		{
			// start time is current time
			int start = time;
			
			// create object for pushing to return vector
			ProcessSwapEvent pushPSE;
			
			// set PID
			pushPSE.processId = incomingProcessList[index].processId;
			
			// set start time
			pushPSE.eventTime = start;
			
			// push to return vector
			listOfSchedulingEvents.push_back(pushPSE);
			
			// response ratio = 1 + (waiting time / runtime)
			// waiting time = startTime - arrivalTime
			float waitingTime = start - incomingProcessList[index].arrivalTime;
			cumulativeWait += waitingTime;
			cumulativeRun += runtime;
			float responseRatio = 1 + (waitingTime / runtime);
			averageResponseRatio += responseRatio;
			cout << "Response ratio: " << responseRatio << endl;
			
			// modify time variable to skip over looping while a process is 'executing'
			// subtract 1 since time is going to increment at the end of the loop
			time += runtime - 1;
			
			// erase the process we 'executed' so we can break when we have no more processes
			incomingProcessList.erase(incomingProcessList.begin() + index);
		}
	}
	cout << "Average Response ratio: " << (averageResponseRatio / processCount) << endl;
	cout << "Cumulative Response ratio: " << (1 + (cumulativeWait / cumulativeRun)) << endl;
	return listOfSchedulingEvents;
}

vector<ProcessSwapEvent>  shortestRemainingTime(vector <ProcessArrivalEvent> incomingProcessList){
	
//	cout << "in shortest remain "<< endl;
	
	
	int num = incomingProcessList.size();
	
	// Used for calculating the cumulative response ratio
	int totalServiceTime = 0;
	for (int i = 0; i < num; i++) {
		totalServiceTime += incomingProcessList[i].runningTime;
	}
	int waitingTime = 0;
	
	vector<ProcessSwapEvent> listOfSchedulingEvents;
	
	// Note: this list contains all waiting processes AND the currently executing process.
	vector<ProcessArrivalEvent> waitingProcesses;
	int activeProcessIndex= -1;

	ProcessArrivalEvent activeProcess;
	
	// Keeps track of the response ratios for each process.
	// The index of a process is its processId
	double responseRatios[num];
	
	unsigned time = 0;
	bool reschedule = false;
	
	// Loop acting as the clock counter.
	// Inside, we check to see if we need to reschedule
	//	(because of an incoming process or a completed process
	// and then we reschedule and run the active process.
	for (time = 0; true; time++) {
		
		// Loop to get all processes that start at the current time
		while (true) {
			if (! incomingProcessList.empty()) {
				// If the first process in the list arrives now:
				if (incomingProcessList[0].arrivalTime == time) {
					// Remove it from the incoming list and put it in the waiting list.
					waitingProcesses.push_back(incomingProcessList[0]);
					incomingProcessList.erase(incomingProcessList.begin());
					// we must reschedule our jobs to look for the shortest remaining time.
					reschedule = true;
				}
				else // there are no more processes that start now.
					break;
			}
			else // there are no more processes
				break;
		}
		
		// If the currently running process is complete
		if ( (activeProcessIndex >= 0) && 
			(waitingProcesses[activeProcessIndex].complete()) ) {
			
			// calculate response ratio.
			ProcessArrivalEvent completed = waitingProcesses[activeProcessIndex];
			double responseRatio = ((double) (time - completed.arrivalTime)) / completed.runningTime;
			responseRatios[completed.processId] = responseRatio;
			
			// Remove from waiting process list.
			waitingProcesses.erase(waitingProcesses.begin() + activeProcessIndex);
			
			reschedule = true;
		}
		
		
		// All of the scheduling work goes here. This only runs if:
		//		1. A new process starts at this time step
		//	OR	2. The previously active process completed its run
		if(reschedule){
			
			if (waitingProcesses.empty() && incomingProcessList.empty()) {
				// We're done.
				break;
			}
			
			if (waitingProcesses.size() > 0) {
				// Find index of shortest remaining process
				int shortestRemainingIndex = 0;
				for (int i = 0; i < waitingProcesses.size(); i++) {
					if(waitingProcesses[i].remainingTime() < waitingProcesses[shortestRemainingIndex].remainingTime() )
						shortestRemainingIndex = i;
				}
				activeProcessIndex = shortestRemainingIndex;
				
				// create new processSwapEvent.
				ProcessSwapEvent pse;
				pse.eventTime = time;
				pse.processId = waitingProcesses[activeProcessIndex].processId;
				listOfSchedulingEvents.push_back(pse);
			}
			else {
				// no currently active process
				activeProcessIndex = -1;
			}

			reschedule = false;
		}
		
		// Debugging info
//		cout << "Time: " << time << endl;
//		cout << "incoming: " << incomingProcessList.size() << endl;
//		cout << "waiting:  " << waitingProcesses.size() << endl;
//		cout << "current:  " << activeProcessIndex << endl;
		
		
		// If any processes are waiting (except for the active process) then increment waitingTime.
		if (waitingProcesses.size() > 1) {
			waitingTime++;
		}
		
		// If there is a process currently active, let it run (increment its active time)
		if (activeProcessIndex >= 0 && activeProcessIndex < waitingProcesses.size()) {
//			cout << "Executing Process: " << waitingProcesses[activeProcessIndex].processId << endl << endl;
			waitingProcesses[activeProcessIndex].activeTime++;
		}
//		cout << endl;
	}
	
	//	The individual response ratios
	cout << "Individual Response Ratios: " << endl;
	for (int i = 0; i < num; i++) {
		cout << "responseRatio[ Process " << i << " ]:\t" << responseRatios[i] << endl;
	}
	cout << endl;
	
	double averageResponseRatio = 0;
	for (int i = 0; i < num; i++)
		averageResponseRatio += responseRatios[i];
	averageResponseRatio /= num;
	
	cout << "Average Response ratio: "<< averageResponseRatio << endl;
	
	double cumulativeResponseRatio = ((double) (waitingTime + totalServiceTime)) / ((double) totalServiceTime);
	cout << "Cumulative Response ratio: "<< cumulativeResponseRatio << endl;
	
	return listOfSchedulingEvents;
}

vector<ProcessSwapEvent>  roundRobin(vector <ProcessArrivalEvent> incomingProcessList, int timeStep){
	 vector<ProcessSwapEvent> listOfSchedulingEvents;
	// CSE410DO
	cout << " in round timestep "<<timeStep <<  endl;
	queue<ProcessArrivalEvent> processQueue;
	bool looping = true;
	int processCount = incomingProcessList.size();
	int timePassed = 0;
	double responseRatio, totalResponseRatio, cumulativeWait, cumulativeRun, waitingTime;

	while(looping){
		ProcessSwapEvent tempPSE;
		ProcessArrivalEvent PAE;		
	
		if( processQueue.empty() ){
			//our queue is empty.  add a new process only if the arrival time is >= the current time
			// and the vector has to not be empty
			if ( incomingProcessList.empty() ){
				// the queue is empty and the vector is empty.  we're done here.
				looping = false;
				
			}else if( incomingProcessList.front().arrivalTime >= timePassed ){
				//push the first element and erase it from the vector
				processQueue.push( incomingProcessList.front() );
				incomingProcessList.erase( incomingProcessList.begin() );
			}else{
				//our queue was empty, but the vector was not
				// increase our time passed
				timePassed += 1;
			}
	
		}
		// check to see if our queue has an item.  This is not an else because we
		// want to see if we queued anything earlier
		if( !processQueue.empty() ){

			
			// our process list isn't empty.  See if its time to add another
			// process to our queue
			if ( !incomingProcessList.empty() ){
				if( incomingProcessList.front().arrivalTime <= timePassed ){
					//push the first element and erase it from the vector
					processQueue.push( incomingProcessList.front() );
					incomingProcessList.erase( incomingProcessList.begin() );
				}
			}
			
			// grab the queued element
			PAE = processQueue.front();
			processQueue.pop();

			//set tempPSE event time.  Starts at 0, each subsequent one
			//is increased.
			tempPSE.eventTime = timePassed;
			tempPSE.processId = PAE.processId;
			
			// reduce time to run
			if( ( PAE.runningTime - PAE.activeTime ) > timeStep ){
				PAE.activeTime += timeStep;
				processQueue.push( PAE );
				timePassed += timeStep;
			}else{
				timePassed += ( PAE.runningTime - PAE.activeTime );	
				PAE.activeTime += ( PAE.runningTime - PAE.activeTime );
			}
			if( PAE.complete() ){
				
			   // cout << "Time Passed: " << timePassed << endl;
			   // cout << "Arrival Time: " << PAE.arrivalTime << endl;
			   // cout << "Running Time: " << PAE.runningTime << endl;
			   // cout << "Waiting Time: " << timePassed - PAE.arrivalTime << endl;
				responseRatio = ( (double)timePassed - (double)PAE.arrivalTime )/ (double) PAE.runningTime + 1;
				cout << "Response ratio: " << responseRatio << endl;
				
				cumulativeWait += ( (double)timePassed - (double)PAE.arrivalTime );
				cumulativeRun += PAE.runningTime;
				totalResponseRatio += responseRatio;
			}

		//	cout << "Response ratio: "<< responseRatio << endl;
			listOfSchedulingEvents.push_back( tempPSE );
		}
		

	
	}
	
		cout << "Average Response Ratio: " << totalResponseRatio / (double) processCount << endl;
		cout << "Cumulative Response Ratio: " << cumulativeWait / cumulativeRun + 1 << endl;
	
	return listOfSchedulingEvents;
}

/*
 * valid command lines are
 * proj03 inputFilename outputFilename -FCFS
 * proj03 inputFilename outputFilename -SPN
 * proj03 inputFilename outputFilename -SRT
 * proj03 inputFilename outputFilename -RR timeStep
 */
int main(int argc, char** argv) {
	string inputFile(argv[1]);
	char *outputFile = argv[2];
	string schedulerArgument(argv[3]);

	vector<ProcessArrivalEvent>  arriveEvents = getProcessArrivalSequence(argv[1]);
	vector<ProcessSwapEvent>  scheduledEvents;
	if (schedulerArgument == "-FCFS"){
		scheduledEvents = firstComeFirstServeScheduler(arriveEvents);
	}else if (schedulerArgument == "-SPN"){
		scheduledEvents = shortestProcessNext(arriveEvents);
	}else if (schedulerArgument == "-SRT"){
		scheduledEvents = shortestRemainingTime(arriveEvents);
	}else if (schedulerArgument == "-RR"){
		int timeStep = atoi(argv[4]);
		scheduledEvents = roundRobin(arriveEvents, timeStep);
	}

	writeOutputToFile(scheduledEvents, outputFile);

	return 0;
}

